package com.future;

/**
 * Description: 215. 数组中的第K个最大元素
 *
 * @author weiruibai.vendor
 * Date: 2022/6/11 10:54
 */
public class Solution_215 {

    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 1, 5, 6, 4};
       // nums = new int[]{5, 3, 2, 6, 4, 1, 9, 3};
        int k = 2;
        nums = new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6};
        k = 4;
        System.out.println(findKthLargest(nums, k));
    }

    public static int findKthLargest(int[] nums, int k) {
        quickSort(nums, 0, nums.length - 1);
        int N = nums.length;
        return nums[N-k];
    }

    private static void quickSort(int[] nums, int L, int R) {
        if (L >= R) {
            return;
        }
        int mid = partition(nums, L, R);
        quickSort(nums, L, mid - 1);
        quickSort(nums, mid + 1, R);
    }

    private static int partition(int[] nums, int L, int R) {
        if (L > R) {
            return -1;
        }

        int lessLeft = L - 1;
        int index = L;
        while (index < R) {
            if (nums[index] <= nums[R]) {
                swap(nums, index, ++lessLeft);
            }
            index++;
        }
        swap(nums, ++lessLeft, R);
        return lessLeft;
    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }


}
